更新某一个状态的价值时，回溯到该状态的所有可能的后续状态
很多时候，我们并不知道环境状态转换模型 \(P_{s s'}^a\)
不基于模型的强化学习问题定义
强化学习的 5 个因素：\(S, A, R\) ，衰减因子 \(\gamma\)，策略 \(\pi\)
Model 方式的定义
这里加上一个 状态转换模型 \(P_{ss'}^a\)
预测问题 求解该策略的状态价值函数 \(v_{ \pi}(s)\)
预测问题就是在该攻略的指导下，我们的电竞选手最高能拿到多少分
\(S, A, R + \gamma + \pi + P\)
控制问题 求解最优的价值函数\(v_{*}\) 和策略\(\pi_{*}\)
让多名电竞选手打一遍，然后看最高的分数。让这名选手写个教程，也就是\(\pi_{*}\)
\(S, A, R + \gamma + P\)
Model-free 方式的定义
预测问题 不变
\(S, A, R + \gamma + \pi\)
控制问题
\(S, A, R + \gamma + \epsilon\) 这里把 \(P\) 换成了 \(\epsilon\)
求解最优的动作价值函数 \(q_{*}\) 和策略\(\pi_{*}\)
蒙特卡罗法求解特点
蒙特卡罗方法
采样法，基本思想是根据一个已知的概率密度函数 \(p(x)\) 的分布来计算函数 \(f(x)\) 的期望。
\[\mathbb{E}[f(x)]=\int_{x} f(x) p(x) d x \]
按概率分布 \(p\) 抽取 \(N\) 个样本 \(x^{(1)}, x^{(2)}, \cdots, x^{(N)}\)， 则 \(f(x)\) 的期望可以用这 \(N\) 个 \(x^{(i)}\) 的均值来近似。
\[\hat{f}_{N}=\frac{1}{N}\left(f\left(x^{(1)}\right)+\cdots+f\left(x^{(N)}\right)\right) \]
蒙特卡罗方法的难点在于 \(p(x)\)难以采样，这里常常采用间接的采样策略，比如拒绝采样、重要性采样、马尔可夫链蒙特卡罗采样等。这些方法一般是先根据一个比较容易采样的分布进行采样，然后通过一些策略来间接得到符合 \(p(x)\) 分布的样本。
马尔可夫链蒙特卡罗方法
适用于高维空间中采样
核心思想是将样过程看作是一个马尔可夫链。
\[\mathbf{x}_{1}, \mathbf{x}_{2}, \cdots, \mathbf{x}_{t-1}, \mathbf{x}_{t},, \mathbf{x}_{t+1}, \cdots \]
第 \(t + 1\)次采样依赖于第 \(t\) 次抽取的样本\(\mathbf{x}_t\) 以及状态转移分布（即提议分布）\(q\left(\mathbf{x} | \mathbf{x}_{t}\right)\)。如果这个马尔可夫链的平稳分布为 \(p(\mathbf{x})\) ，那么在状态平稳时抽取的样本就服从 \(p(\mathbf{x})\) 的分布。
蒙特卡罗法的特点
一是和动态规划比，它不需要依赖于模型状态转化概率。二是它从经历过的完整序列学习，完整的经历越多，学习效果越好。
蒙特卡罗法求解强化学习预测问题
预测问题就是策略评估
对于蒙特卡罗法来说，如果要求某一个状态的状态价值，只需要求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解
\[\begin{array}{c}{G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \gamma^{T-t-1} R_{T}} \\ {v_{\pi}(s) \approx \operatorname{average}\left(G_{t}\right), s . t . S_{t}=s}\end{array} \]
注意这里\(G_t\) 和 \(v_{\pi}(s)\) 的关系。
两个可以优化的点：
第一个点是同样一个状态可能在一个完整的状态序列中重复出现，那么该状态的收获该如何计算？
- 首次访问
- 每次访问
第二个点是累进更新平均值。这里是针对 average 优化，不必保存所有状态的 reward 再取平均。改进方法是，每次保存上一轮迭代的 reward 均值和次数，计算当前轮时，参考这个公式
\[\mu_{k}=\frac{1}{k} \sum_{j=1}^{k} x_{j}=\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right)=\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right)=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right) \]
蒙特卡罗法求解强化学习控制问题
- 蒙特卡罗方法一般是优化动作价值函数 \(q_{*}\)，而不是状态价值函数 \(v_{*}\);
- 蒙特卡罗方法采用 \(\epsilon-greedy\) 方法更新
\[\pi(a|s)= \begin{cases} \epsilon/m + 1- \epsilon & {if\; a^{*} = \arg\max_{a \in A}Q(s,a)}\\ \epsilon/m & {else} \end{cases} \]
在实际求解过程中，\(\epsilon\) 一般会随着迭代逐渐减小。前期勇于探索，后期精益求精。
蒙特卡罗法控制问题算法流程
- 输入：\(S, A, R, \gamma, \epsilon\)
- 输出：\(q_{*}, \pi_{*}\)
- 初始化动作价值 \(Q(s, a) = 0\)，状态次数 \(N(s, a) = 0\)，采样次数 \(k = 0\)，随机初始化策略 \(\pi\)
- 第 \(k\) 次蒙特卡罗采样，得到一个完整的状态序列\(S_1,A_1,R_2,S_2,A_2,...S_t,A_t,R_{t+1},...R_T, S_T\)
- 对于序列里出现的每一状态对 \((S_t, A_t)\)，计算器收获 \(G_t\)，更新其计数 \(N(s, a)\) 和行为价值函数 \(Q(s, a)\) \[\begin{array}{c}{G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \gamma^{T-t-1} R_{T}} \\ {N\left(S_{t}, A_{t}\right)=N\left(S_{t}, A_{t}\right)+1} \\ {Q\left(S_{t}, A_{t}\right)=Q\left(S_{t}, A_{t}\right)+\frac{1}{N\left(S_{t}, A_{t}\right)}\left(G_{t}-Q\left(S_{t}, A_{t}\right)\right)}\end{array} \]
- 基于计算出的动作价值函数，更新当前的 \(\epsilon-greedy\) 策略 \[\begin{array}{c}{\epsilon=\frac{1}{k}} \\ {\pi(a | s)=\left\{\begin{array}{ll}{\epsilon / m+1-\epsilon} & {\text { if} a^{*}=\arg \max _{a \in A} Q(s, a)} \\ {\epsilon / m} & {\text { else}}\end{array}\right.}\end{array} \]
- 如果所有的 \(Q(s, a)\) 收敛，则得到 \(q_{*}\) 和 \(v_{*}\)。
蒙特卡罗法求解强化学习问题小结
第一个不基于模型的强换学习问题求解方法，可以不知道环境状态转换模型 \(P_{s s'}^a\)，求解时间复杂度低。
缺点是，每次采样都需要一个完整的状态序列。